/*
 *    Copyright 2011-2012 19lou.com
 */
package com.tech.utils;

import java.io.Serializable;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author liuyong 2013-1-31
 */
public class MyTreeApp implements Serializable {

    private Map<Character,Node> nodes = new HashMap<Character, Node>();
    
    public void add(String words){
        char[] cs = words.toCharArray();
        Node prefixNode = null;
        if (nodes.containsKey(cs[0])){
            prefixNode = nodes.get(cs[0]);
            if (cs.length == 1){
                prefixNode.setWord(true);
            }else{
                for(int i = 1; i < cs.length; i++){
                    if (prefixNode.getNext(cs[i]) != null && prefixNode.getNext(cs[i]).getC() == cs[i]){
                        prefixNode = prefixNode.getNext(cs[i]);
                        if (i + 1 == cs.length){
                            prefixNode.setWord(true);
                        }
                    }else{
                        char[] cc = new char[cs.length - i];
                        System.arraycopy(cs,i,cc,0,cs.length - i);
                        prefixNode.setNext(cc[0],buildNode(cc));
                        break;
                    }
                }
            }
        }
        if (prefixNode == null){
            nodes.put(cs[0],buildNode(cs));
        }
    }
    
    public Set<String> analyzer(String word){
        Set<String> ss = new HashSet<String>();
        char[] cs = word.toCharArray();
        for (int i = 0; i < cs.length; i++){
            if (nodes.containsKey(cs[i])){
                StringBuilder sb = new StringBuilder();
                sb.append(cs[i]);
                Node prefixNode = nodes.get(cs[i]);
                if (prefixNode.isWord()){
                    ss.add(sb.toString());
                }
                for (int j = i + 1; j < cs.length; j++){
                    Node next = prefixNode.getNext(cs[j]);
                    sb.append(cs[j]);
                    if (next == null){
                        break;
                    }else if (next.isWord()) {
                        ss.add(sb.toString());
                    }
                    prefixNode = next;
                }
            }
        }
        return ss;
    }
    
    private Node buildNode(char [] cs){
        Node root = null;
        Node parent = null;
        for (int i = 0; i < cs.length; i++){
            Node node = new Node();
            node.setC(cs[i]);
            node.setWord(i + 1 == cs.length);
            if (parent != null){
                parent.setNext(cs[i],node);
            }else{
                root = node;
            }
            parent = node;
        }
        return root;
    }
    
    public static void main(String[] args){
        MyTreeApp treeApp = new MyTreeApp();
        treeApp.add("a");
        treeApp.add("ab");
        treeApp.add("abc");
        treeApp.add("abcd");
        treeApp.add("bcd");
        treeApp.add("c");
        
        Set<String> s = treeApp.analyzer("abcdefg");
        
        for (String w : s){
            System.out.println(w);
        }
    }
    
    

    public static class Node implements Serializable {
        
        public static final long serialVersionUID = 1L;
        
        private char c;
        
        private Map<Character,Node> next = new HashMap<Character,Node>();

        private boolean isWord;

        public char getC() {
            return c;
        }

        public void setC(char c) {
            this.c = c;
        }

        public Node getNext(Character key) {
            return next.get(key);
        }

        public void setNext(Character key, Node node) {
            next.put(key,node);
        }

        public boolean isWord() {
            return isWord;
        }

        public void setWord(boolean word) {
            isWord = word;
        }
    }
}

